1737D - Ela and the Wiring Wizard - CodeForces Solution

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
template<class T, class S>
ostream& operator << (ostream &o, const pair<T, S> &p) {
    return o << '(' << p.first << ", " << p.second << ')';
}
template<template<class, class...> class T, class... A>
typename enable_if<!is_same<T<A...>, string>(), ostream&>::type
operator << (ostream &o, T<A...> V) {
	o << '[';
	for(auto a : V) o << a << ", ";
	return o << ']';
}

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;

#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define F(i, l, r) for(ll i = l; i < (r); ++i)
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define P(a, n) { cout << "{ "; F(_, 0, n) cout << a[_] << " "; cout << "}\n"; }
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define K first
#define V second
#define M 1000000007 //998244353
#define N 510

ll d[N][N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    G(tc) while(tc--) {
        G(n) G(m)
        vector<pair<pl, ll>> edges;
        F(i, 1, n + 1) fill_n(d[i], n + 1, LLONG_MAX), d[i][i] = 0;
        F(i, 0, m) {
            G(u) G(v) G(w)
            edges.emplace_back(pl{u, v}, w);
            d[u][v] = d[v][u] = 1;
        }
        F(k, 1, n + 1) F(i, 1, n + 1) F(j, 1, n + 1) if(d[i][k] != LLONG_MAX && d[k][j] != LLONG_MAX)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        ll ans = LLONG_MAX;
        for(auto e : edges) {
            ll u = e.K.K, v = e.K.V, w = e.V;
            ans = min({ans, w * (d[u][1] + d[v][n] + 1), w * (d[u][n] + d[v][1] + 1)});
            F(i, 1, n + 1) ans = min(ans, w * (min(d[u][i], d[v][i]) + d[i][1] + d[i][n] + 2));
        }
        cout << ans << '\n';
    }
}